/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    ListNode* head, * tail;
    head = tail = NULL;
    ListNode* h1 = list1, * h2 = list2;
    while (h1 && h2)
    {
        if (h1->val < h2->val)
        {
            if (!head)
                head = tail = h1;
            else
            {
                tail->next = h1;
                tail = tail->next;
            }
            h1 = h1->next;
        }
        else
        {
            if (!head)
                head = tail = h2;
            else
            {
                tail->next = h2;
                tail = tail->next;
            }
            h2 = h2->next;
        }
    }
    while (h1)
    {
        if (!head)
            head = tail = h1;
        else
        {
            tail->next = h1;
            tail = tail->next;
        }
        h1 = h1->next;
    }
    while (h2)
    {
        if (!head)
            head = tail = h2;
        else
        {
            tail->next = h2;
            tail = tail->next;
        }
        h2 = h2->next;
    }
    return head;
}